package com.liunian.algorithmstudy.greedy;

import java.util.Arrays;

public class LargestSumAfterKNegations1005 {

	public int largestSumAfterKNegations(int[] nums, int k) {
		int sum = 0;
		for (int i = 0; i < nums.length; i++) {
			if (nums[i] < 0 && k > 0) {
				nums[i] = -nums[i];
				k--;
			}
			sum += nums[i];
		}
		Arrays.sort(nums);
		return sum - (k % 2 == 0 ? 0 : 2 * nums[0]);
	}

	public static void main(String[] args) {
		LargestSumAfterKNegations1005 l = new LargestSumAfterKNegations1005();
		System.out.println(l.largestSumAfterKNegations(new int[]{-4,-2,-3}, 4));
	}

}
